# Edges and vertices of a tree.
We say a graph $T = (V,E)$ is a tree, if it is a **connected graph** where there is **no cycles**.
## Unique path between two vertices in a tree.
Suppose $x,y$ are any two vertices in a tree $T$.
Suppose $x = y$. If there is a nontrivial path from $x$ to itself, then we have a cycle, a contradiction.
Now suppose $x \neq y$. Suppose there are two different paths from $x$ to $y$. Call these paths $A$ and $B$, say $$
\begin{align*}
A &=\langle x = a_{1}, \dots, a_{k} = y \rangle \\
B &= \langle x = b_{1}, \dots, b_{\ell} = y \rangle
\end{align*}
$$ Along both paths, start from $x$ and let $p$ be the vertex just before the two paths differ. This $p$ exists and it could be $x$. Namely $p = a_{r}$ where $r =\max \{i:a_{j}=b_{j} \text{ for all } 1 \le j \le i \}$. Then the vertex after $p$ on paths $A$ and $B$ are different. Continue along each path until we hit a vertex $q$ to be the first vertex the paths have in common after $p$. This vertex $q$ exists and it could be $y$. Namely, $q = a_{r'}$ where $r' = \min \{i > r: a_{i} = b_{j} \text{ for some } j > r\}$. Then the two paths from $p$ to $q$ forms a cycle in $T$, a contradiction.
Hence a tree admits only a unique path between any two vertices.
## Leaves and internal vertices.
We will call a vertex with degree $1$ as a **leaf**. If a vertex has degree $\ge 2$ then we call it an **internal vertex**. Depending on convention, we can define a vertex of degree $0$ as a leaf as well.
If a tree has $2$ or more vertices, then it has at least two leaves.
Indeed, start from any vertex $x$ in this tree. Pick any edge joining to $x$, to the vertex $t_{1}$. And repeat picking edges where it joins to a vertex we have not seen before. We repeat this until we cannot. Then we reach a vertex of degree 1, say $p$. Then repeat the same on $p$, starting a new path. This reaches another leaf $q$.
## Number of vertices and edges in a tree.
If $T=(V,E)$ is a tree, then $|V|= |E|+1$.
Induction on the number of vertices. And induct by removing a leaf vertex.